package randomthoughts.dp;

/**
 * @author tongchen
 * @create 2023-04-15 21:15
 */
public class TheWeightOfLastStone {
    public static void main(String[] args) {

    }

    /**leetCode 1049
     * 动规五部曲：1.dp[i]:i容量下所能容纳最大的石头重量 i代表容量 2.递推公式：dp[i]=max(dp[i],dp[i-weight[i]]+value[i])
     * 3.初始化：dp[0]=0 ;4.遍历方式：一层是物品，二层是容量，容量从后往前遍历
     * @return
     */
    public static int theDValue(int[]stones){
        //创建和
        int sum=0;
        //遍历数组
        for (int i:stones) {
            sum+=i;
        }
        //创建target
        int target=sum/2;
        //创建dp数组
        int[]dp=new int[target+1];
        //循环
        for(int i=0;i<stones.length;++i){
            for (int j=target;j>=stones[i];--j){
                dp[j]=Math.max(dp[j],dp[j-stones[i]]+stones[i]);
            }
        }
        return sum-2*dp[target];
    }
}
